import java.util.*;

/**
* @description: 967. 连续差相同的数字
* @author hewei
* @date 2022/9/27 14:47
* @version 1.0
*/

public class NumsSameConsecDiff {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new NumsSameConsecDiff().numsSameConsecDiff(3, 7)));
    }

    int target;
    public int[] numsSameConsecDiff1(int n, int k) {
        target = n;
        return process(n, k);
    }

    public int[] process(int n, int k) {
        if (n == 1) {
            return new int[]{0,1,2,3,4,5,6,7,8,9};
        }
        int[] nums = process(n - 1, k);
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            int temp = num;
            String s = String.valueOf(num);
            if (s.length() != n - 1) {
                num = 0;
            } else num = s.charAt(0) - '0';
            if ((num + k <= 9 && num + k > 0) || (num + k == 0 && n != target)) {
                list.add((int) ((num + k) * Math.pow(10, n - 1) + temp));
            }
            if (num + k != num - k)
            if (num - k > 0 || (num - k == 0 && n != target)) {
                list.add((int) ((num - k) * Math.pow(10, n - 1) + temp));
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public int[] numsSameConsecDiff(int n, int k) {
        Deque<String> queue = new LinkedList<>();
        for (int i = 0; i <= 9; i++) {
            queue.add(String.valueOf(i));
        }
        for (int i = 1; i < n; i++) {
            int size = queue.size();
            while (size-- > 0) {
                String poll = queue.poll();
                int c = poll.charAt(0) - '0';
                String temp;
                if ((c + k <= 9 && c + k > 0) || (c + k == 0 && i != n - 1)) {
                    temp = c + k + poll;
                    queue.add(temp);
                }
                if (c + k != c - k && (c - k > 0 || (c - k == 0 && i != n - 1))) {
                    temp = c - k + poll;
                    queue.add(temp);
                }
            }
        }
        int[] ans = new int[queue.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = Integer.parseInt(queue.poll());
        }
        return ans;
    }
}
